# 作者: YYJ
# 2025年06月12日22时09分31秒
# 2486249622@qq.com

class Node:
    def __init__(self, ele=1, left=None, right=None):
        self.element = ele
        self.left = left
        self.right = right


class Tree:
    def __init__(self):
        self.root = None
        self.queue = []  # 辅助队列

    def build(self, value):
        new_node = Node(value)
        self.queue.append(new_node)  # 入队
        if self.root is None:
            self.root = new_node
        else:
            if self.queue[0].left is None:
                self.queue[0].left = new_node
            else:
                self.queue[0].right = new_node
                self.queue.pop(0)

    def preorder(self, node: Node):
        if node:
            print(node.element, end=' ')
            self.preorder(node.left)
            self.preorder(node.right)

    def inorder(self, node: Node):
        if node:
            self.inorder(node.left)
            print(node.element, end=' ')
            self.inorder(node.right)

    def postorder(self, node: Node):
        if node:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.element, end=' ')

    def level_order(self, node: Node):
        self.queue.clear()
        self.queue.append(node)
        while self.queue:
            node = self.queue.pop(0)
            print(node.element, end=' ')
            if node.left:
                self.queue.append(node.left)
            if node.right:
                self.queue.append(node.right)


if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 10):
        tree.build(i)

    tree.preorder(tree.root)  # 前序遍历
    print()
    tree.inorder(tree.root)  # 中序遍历
    print()
    tree.postorder(tree.root)  # 后序遍历
    print()
    tree.level_order(tree.root)  # 层序遍历
    print()
